Round Overview
Discuss this match
SRM 586 problem set was a production of gojira_tc. A interesting combination of careful analysis problems. Division 1 coders were greeted by what seemed to be a geometric twist of a common trope in algorithm contests - an optimization problem in which you need to consider only the end points of intervals. Many coders fell prey to this rushed assumption, which enabled many successful challenges. Coders like tomerun, however, were able to solve the problem correctly and quite fast - less than 4 minutes. The second problem required more implementation work not in disregard of thinking of a correct solution. Petr got the high score in around 10 minutes. The hard problem required you to quickly find and exploit special properties in a specific kind of string. This time Egor got the fastest solution. That feat, combined with multiple challenge wins lead Egor to the first place with a notable lead of almost 800 points. Vasyl[alphacom] was second thanks to consistent submission speed in all three problems. Challenge success allowed vlad89 and kraskevich to get the third and fourth places without solving the hard problem. The hard problem, however, allowed semiexp to claim the fifth place.
In Division 2, many coders solved all three problems and it was thus required to do far more in order to prevail. A very fast hard submission and consistent speed in the other two problems allowed feyat to earn the first place.
SRM 586 was no ordinary match. It was the first SRM to officially allow the Python programming language in submissions. We hope this enables more coders to join us in TopCoder contests.
Used as: Division Two - Level One:
Value | 250 |
Submission Rate | 797 / 1009 (78.99%) |
Success Rate | 709 / 797 (88.96%) |
High Score | i_want_passion for 249.58 points (1 mins 9 secs) |
Average Score | 172.11 (for 709 correct submissions) |
This is an implementation problem, we can just simulate the actions of each team captain. There will be n player selection turns. If we index the turns from 0 to n-1, captain 1 will have the even turns and captain 2 the odd turns.
In each turn, the respective captain should pick the player that he prefers the most and that hasn’t been picked before. To simplify the code, we can just make a 2D array prefs, prefs[0] holds preference1 - the preferences to use in even turns. prefs[1] holds preference2 - the preferences for odd turns. So in each turn i we use prefs[ i % 2 ], where i % 2 is the remainder after dividing by 2.
One approach is to remember the teams assigned to each player as ‘1’ and ‘2’ (as the result format asks us to) or ‘?’ if he was not assigned yet. In each turn, find the smallest index j of prefs[i%2] that hasn’t been assigned yet (prefs[i%2][ j ] has ‘?’ assigned to it). After finding this j, assign its team. Like in the following c++ code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string simulate(vector < int > preference1, vector < int > preference2) {
int n = preference1.size();
// Make the prefs[] 2D array, or vector of vectors in this case:
vector < vector < int > > prefs = {
preference1,
preference2
};
string res(n, '?');
for (int i = 0; i < n; i++) {
// Find smallest index in prefs[i%2] of an unassigned player:
int j = 0;
while (res[prefs[i % 2][j] - 1] != '?') {
j++;
}
// assign the player:
res[prefs[i % 2][j] - 1] = '1' + (i % 2);
}
return res;
}
An alternative is to remove the player from both preferences after picking him for a team. In each turn each captain picks the first player in his preferences list (Which is guaranteed to not have a team yet, else he would have been removed from the list). Like in the following python code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def simulate(self, preference1, preference2):
n = len(preference1);
# Make the prefs[] 2 D array:
prefs = [list(preference1), list(preference2)];
# the team assignments
res = ['0'] * n
for i in range(0, n):
p = prefs[i % 2][0]
#remove player from both lists:
prefs[0].remove(p)
prefs[1].remove(p)
#assign this team to the player:
res[p - 1] = str(1 + (i % 2)) #if even,
return 1,
else 2.
# res is a list, the result must be a string:
return string.join(res, '')
PiecewiseLinearFunctionDiv2
Problem Details
Used as: Division Two - Level Two:
Value | 500 |
Submission Rate | 546 / 1009 (54.11%) |
Success Rate | 425 / 546 (77.84%) |
High Score | Asadonn for 499.98 points (0 mins 12 secs) |
Average Score | 344.18 (for 425 correct submissions) |
There are various queries, but we can just treat each query individually: For a integer y, how many solutions are there to the equation: `f(x) = y`? The function is defined a set of segments: For each `(i > 0)`, the function includes the segment between points `(i-1, Y[i-1])` and `(i, Y[i-1])`. Let us start there. Graphically, the question: how many times does equation `f(x) = y` intersect with any of the segments of `f()` ?
There are three kinds of segments:
When `(Y[i-1] < Y[i])` we have a decreasing segment. In this case, there will be an intersection with `y` if and only if `(Y[i-1] <= y <= Y[i])`.
When `(Y[i-1] = Y[i])`, the segment is perfectly horizontal. If `(y = Y[i] = Y[i-1])`, we will see that the lines coincide, this means that there are infinitely many (all the values of `(i-1 <= x <= i)`) solutions to the equation. In this special case, the result is -1.
When `(Y[i-1] > Y[i])`, there will be an intersection with `y` if and only if `(Y[i-1] >= y >= Y[i])`.
It would appear that we can simply count the number of times y intersects with each of the segments using that formula and we will find the result for the number of intersections with f(). There is something that complicates this approach. For each two consecutive segments, there is a point that is shared by both segments. If this point is an intersection, it should only count once:
In the example we have `(y = Y[i])` which means that `(Y[i-1] >= y >= Y[i])` and `(Y[i] <= y <= Y[i+1])` are both true, however there is only one intersection. To work around this, notice this can only happen if `(y = Y[i])` for some i. We can change the inequalities to: `(Y[i-1] > y > Y[i])` and `(Y[i] < y < Y[i+1])`, this time the intersections will be ignored by the inequalities whenever `y` is exactly equal to one of the ends of a segment. We can count those cases separately, the number of times `y` appears as an end of a segment is equal to the number of times `y` appears in `Y[]`.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class PiecewiseLinearFunctionDiv2:
# count the number of solutions
for a single value of y:
def countSolutionsY(self, Y, y):
c = Y.count(y) # First count how many times y appears in Y[]
for i in range(1, len(Y)):
if (Y[i] == y) and(y == Y[i - 1]):
# Special
case: y appears two consecutive times:
return -1
#
if (Y[i - 1] < y < Y[i])(when Y[i - 1] < Y[i])
# or(Y[i - 1] < y < Y[i])(when Y[i - 1] > Y[i])
.
# increase by 1.(Note that we can simplify the condition as):
c += (min(Y[i], Y[i - 1]) < y < max(Y[i], Y[i - 1]))
return c
def countSolutions(self, Y, query):
return [self.countSolutionsY(Y, y) for y in query]
StringWeightDiv2
Problem Details
Used as: Division Two - Level Three:
Value | 1000 |
Submission Rate | 68 / 1009 (6.74%) |
Success Rate | 47 / 68 (69.12%) |
High Score | feyat for 919.96 points (8 mins 31 secs) |
Average Score | 599.75 (for 47 correct submissions) |
Before we get into counting these strings, we should understand their properties.
Like the first two examples show. In cases with small L, there are ways to make letters contribute a flat 0 to the weight. This is the smallest possible contribution. By definition: `(R >= L)` therefore: `(R - L >= 0)`. Since we want to minimize the total weight, we should try to make most if not all letters contribute 0.
It is possible to make all letters cost 0. Simply make all letters in the string unique: “acwh”. Then for each letter: `(R = L)`. However, we only have 26 available letters. Therefore, we can only make each letter in the string unique when `(L <= 26)`. In that case, we have to use `L` different letters.
When `(L > 26)`, things will change. Let us begin with the smallest of such cases: `(L = 27)`:
If all letters were equal, then for this letter, `(R = 26)` and `(L = 0)`. The total weight is 26.
Perhaps it is better to have as many cost-0 letters as possible? As many letters that appear only once. If we use 25 unique letters, there are two remaining positions that must be used by a repeated letter. We are in a interesting situation: 25 letters contribute exactly 0, regardless of their position and we have two positions used by the same letter. We can pick L and R as the two positions used by this letter. The final weight will be `R-L`, so we want them to be as close as possible, let us make them consecutive , this means that the cost is 1. As long as 25 letters appear exactly once and the remaining letter appears twice but in consecutive positions. The minimum string weight is 1.
But how about larger cases? For L = 40. We can try the same logic, make 25 letters appear exactly once and a final letter appear exactly 15 times. The positions of the 25 letters do not matter, so we only care about L and R for the letter that appears 15 times. We should make the difference `(R - L)` as small as possible. Once again, it is most convenient to make the 15 letters appear consecutively. As long as we do this, the result will be: 14. If L is the first position, then the 15 positions of the letter will be: `(L, L+1, L+2, … , L+13, R = L+14)`.
But we should be critical, although this strategy seems to minimize the total weight, is it the only strategy that manages to do it? In the previous idea, we had 25 letters that appear exactly once and one letter that appears 15 times. However, what about a small change? What about having 24 letters that appear once, 1 letter that appears twice and one letter that appears 14 times? The sum is still 40. Once again, we can ignore the positions of the 24 letters (0 weight). The positions of the other letters are also not important as long as the repetitions are consecutive. If we make sure they are consecutive, the cost of the letter that appears twice will be 1: `(L, R = L+1)`. For the other letter, the cost is 13: `(L, L+1, L+2, …, L+12, R = L+13)`. The total weight is interestingly, 14: 13 + 1. This is also the weight we assumed to be minimum!
It seems that making sure 25 letters appear exactly once is not necessary to minimize the weight. However, making sure that repetitions are always consecutive still seems important. Let us put some detail.
Assume that the only thing we know about a sequence is that it has 26 different letters and repetitions are always consecutive. Let us calculate the weight of the string. Let us say the first letter appears `K_1` times, then it will fill positions `(0, 1, … , K_1-2, K_1 - 1)`. It will contribute `(K_1 - 1)` to the weight. The second letter appears `K_2` times: `(K_1, K_1+1, … , K_1 + K_2 - 2 , K_1 + K_2 - 1)` and therefore contributes `(K_2 - 1)` to the weight. And so and so. The total weight will be: `(K_1 - 1) + (K_2 - 1) + … + (K_26 - 1)`. The total amount of letters is `L` , therefore: `(K_1 + K_2 + … + K_26 = L)`. If we tweak things, you can find that the total weight will be: `(L - 26)`. This formula does not depend on the actual number of times each letter appears in the string. And it seems to be the minimum. This also shows that not using all 26 available letters will only yield a higher weight. E.g: if we use only 20 of the available letters the weight will be: `(L - 20)`.
In order to show that this is the minimum, let us prove that not keeping the repetitions consecutive will always yield a larger weight. If we wish to place `K` letters `a` in the string, making them consecutive will make it contribute `(K-1)` to the weight. If they are not consecutive, then there is at least one other letter `b` that will be between the two extremes of the letter in question. This will increase the weight contributed by letter `a`. The weight contributed by letter `b` will either stay equal (if all its instances are consecutive and between the `a` letters) or also worsen. This means that keeping all repetitions consecutive will yield the minimum weight. That this weight is `(L - 26)` and that any other strategy will increase the weight.
If `(L <= 26)`, then each letter in the string must be unique. So what is the cost of making a string of `L` unique letters, where there are 26 available letters in the alphabet? For the first position, we have 26 options. The second position has 25 options (we cannot use the same letter as the first position). Third position has 24 options and so and so. Therefore, the number of strings is:
`26 * 25 * 24 * … * (26 - L + 1)`
In this case, we need to count the number of strings that follow some properties:
Each letter in the alphabet (26 options) must appear at least once in the string.
All the repetitions in the string must be consecutive.
How can we count the number of strings?
Let us define `f(a, L)` as the number of ways to build a string of length `L` that follows those properties using an alphabet of `a` different letters.
A base case: `(L = 0)`, all the `a` letters must be inserted at least once. If `(a > 0)`, then there is a letter in the alphabet that we cannot use, because there are 0 spaces left, the result is 0. If `(a = 0)`, then there are no more letters to include and no spaces, the total numbers to do it is 1.
In another case, `(L > 0)` and `(a = 1)`, there is only one letter available, we better fill all the `L` positions with it. There is only one way to do this.
When `(L > 0)` and `(a > 1)` , then we have `a` choices for the letter to use in the first positions of the string. The number of those positions can be any `i` : `(1 <= i <= L)`. After using this letter in the first `i` positions, we still need to fill the remaining positions. There are `L-i` remaining positions and we cannot use the letter that we already used. So the partial result is: `a * f(a - 1, L - i)`. We should add together the results for each i, so:
`f(a > 1, L > 0) = sum_(i = 1)^(i <= L)( a * f(a - 1, L - i) )`
There are 27 possible values for `a` and `O(L)` values for `L`. Each time we call the function, we might need `O(L)` steps to perform the sum. If we use dynamic programming or simple memoization to ensure that each argument combination for the function is evaluated at most once, then the algorithmic complexity will be: `O(A * L * L)` where `A` is the size of the alphabet, 26 in this case. This complexity is low enough for the time limit.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static
const int MOD = 1000000009;
long dp[27][1001];
long onceConsecutive(int a, int L) {
long & res = dp[a][L];
if (res == -1) {
if (L == 0) { // base case
res = (a == 0);
} else if (a == 1) {
res = 1;
} else {
// calculate the sum. (We need to use modular arithmetic)
res = 0;
for (int i = 1; i <= L; i++) {
res += (a * onceConsecutive(a - 1, L - i)) % MOD;
}
res %= MOD;
}
}
return res;
}
int countMinimums(int L) {
memset(dp, -1, sizeof(dp));
long res = 1;
if (L <= 26) {
// The simple case:
//26 * 25 * 24 * ...
for (int i = 0; i < L; i++) {
res = (res * (26 - i)) % MOD;
}
} else {
// each letter must appear at least once, all instances
// of each letter must be consecutive.
res = onceConsecutive(26, L); //Use the recurrence relation
}
return res;
}
An alternative solution. We will separate the decision in two parts: a) The order in which the 26 letters are used and b) The number of positions each letter (In the order picked by a) ) will take in the string.
The order of letters is a permutation. The total number of ways to pick the order is: `26!`. Where `n!` is notation for the factorial of `n`.
Now that the order of the letters is picked, we decide the number of positions each letter will take. The total number of positions is `L` . How many solutions are there to the equation: `(K_1 + K_2 + … K_25 + K_26 = L)` where each `K_i > 0`.
To calculate this we can use the following trick: We have to place L stones in 26 boxes. We can picture this as placing separators between some of the stones. For example: oooo|ooo|oo|oo|o means placing 4 stones in the first box, 3 stones in the second, 2 stones in the third, 2 stones in the fourth, and 1 stone in the fifth box.
For 26 boxes, there will be 25 separators. Since each box must have at least one stone, each position between stones can have zero or one separator. We have `L` stones, therefore `(L − 1)` possible places for separators. We need to pick 25 places to put a separator in out of `(L − 1)`. The value is: `C(L - 1, 25)`, where `C()` is the binomial coefficient.
The final result is: `26! * C(L - 1, 25)`.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# define
function f() as the factorial:
from math
import factorial as f
def C(n, k):
return f(n) / f(k) / f(n - k)
#Calculates weight without the modulo
def Weight(L):
if L <= 26:
# 26 * 25 * 24 * ...
# the same as saying 26!/ ( (26 - L)! )
return f(26) / f(26 - L)
else:
# 26! * C(L - 1, 25)
return f(26) * C(L - 1, 25)
class StringWeightDiv2:
def countMinimums(self, L):
return Weight(L) % 1000000009 # Takes the remainder from the result
PiecewiseLinearFunction
Problem Details
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 623 / 661 (94.25%) |
Success Rate | 307 / 623 (49.28%) |
High Score | tomerun for 245.35 points (3 mins 55 secs) |
Average Score | 184.70 (for 307 correct submissions) |
From the explanation for the division 2 version of the problem. We now how to calculate, given a value of y, the number of solutions for `(f(x) = y)`. The number of times the horizontal line at `y` intersects with the function.
The question is how to find the maximum number of solutions that are possible. We should find the value of y that has the maximum number of solutions. Due to the constraints, y could be a real number from -109 to 109. A simple search wouldn’t work fast enough.
The approach in these problems is usually to cut the number of important candidates of y. If we only needed to check for few values instead of all of them we would have solved the problem.
A rushed analysis and prior experience may lead us to believe that only the values from Y[] , the segment end points, are important. But this analysis would be flawed. Problems in which such a trick work are usually related to intervals (Like the recent EelAndRabbit. This problem actually has segments. A interesting feature of these segments is that the intersection with the end of a segment counts only once when the point is shared by two segments.
So we should avoid such rushed ideas and start from scratch. Imagine that we will find the important points from lowest to highest. The points in which the number of solutions changes from smaller points.
The lowest point in which there is a change in the number of solutions is when `y = min(Y[i])`, when y is equal to the smallest value in Y[], this is a moment when the number of solutions changes from zero to something else.
Let us move y. Interestingly, if we move y by a small amount, something interesting will happen: There will now be two solutions for the function. This hints us that considering only points equal to a Y[i] is likely not a good solution. This is precisely because there were two segments that had an intersection with y before moving it slightly up.
We can increase y more and the number of solutions will not change from two. It will not change until we hit the next value that is equal to some Y[i].
The number of solutions changes again.
This time, advancing hasn’t changed the number of solutions. It is because the previous Y[i] was not a common point between two segments, only one.
The number of solutions has changed, although this time for the worse. Another time in which a value of Y[i] is relevant.
The number of solutions changes again after moving y slightly up. This time again for the worse, but this is another situation in which the number of solutions is different in Y[i] and a point that is strictly between Y[i] and Y[i+1]. Note that any real value that is strictly between these two limits will yield the same result.
The last relevant point. This time there are infinitely many solutions. This is a special case, when two consecutive values of Y are equal, there is a value of y that yields infinite solutions and the overall result should be -1
We are ready, this analysis is all that we needed. For a given f(), then we know that the points Y[i] are important, and such we should treat them as candidates. But also the points strictly between two values Y[i] and Y[j] such that Y[j] is the smallest value that is larger than Y[i] can have a different solution. However, any point strictly between Y[i] and Y[j] will yield the same result. We only need to test one of them.
In the example we didn’t really need to test those points strictly between the segment end points, because the final result depended on a Y[i] anyway. But we can use this knowledge to build a challenge case.
We know that it is needed to try points different to Y[i]s when the function has a pair of segments like this:
However, at the moment there is a Y[i] that has two intersections. What we can do is nullify its benefit by adding another V-shape:
So our result is Y = { 2, 4 , 3, 5 }. As you can see, if we use the Y[i]s, we will only have 1, 2, 2 or 1 solutions, respectively. However, if we use y = 3.5, we can have 3 solutions.
The previous case should underline that there at time when the value of y has to be non-integer. Remember the rule, we need any value of y strictly between two Y[i]s. We can just try to iteratively pick each pair (Y[i], Y[j]) and just get the middle point. However, because all Y[i]s are integers, we can even do something as simple as adding 0.5 to each Y[i]. If we try all Y[i] and (Y[i] + 0.5) values, it should be enough to cover all the locations that could have a maximum number of solutions. A python implementation follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def maximumSolutions(self, Y):
# special
case,
if there are two consecutive equal values in Y,
# then we can pick them and the number of solutions is infinite:
for i in range(1, len(Y)):
if Y[i - 1] == Y[i]:
return -1
mx = 0
for z in Y:
for y in (z, z + 0.5): # Try each Y[i] and each Y[i] + 0.5
# Like in division 2 500, first count the number of times
# y = a Y[i]:
c = Y.count(y)
# now count the number of times y is strictly inside
# a segment 's interval:
for i in range(1, len(Y)):
c += (min(Y[i - 1], Y[i]) < y < max(Y[i - 1], Y[i]))
# Keep the maximum we find:
mx = max(mx, c)
return mx
Used as: Division One - Level Two:
Value | 500 |
Submission Rate | 162 / 661 (24.51%) |
Success Rate | 129 / 162 (79.63%) |
High Score | Petr for 442.01 points (10 mins 34 secs) |
Average Score | 247.14 (for 129 correct submissions) |
We are tasked with performing up to 50 queries to find if each query is consistent. Each query simply adds a new battle to the history. We can approach the problem as answering: “Is this list of battles possible / consistent?”. Then we just need to ask this question once for each query, adding the query to the list of battles.
There is plenty of parsing to do in this problem, so we will just assume the parsing was done. We have a 2D table `T` such that `T[i][j]` gives us the j-th time for the i-th nation. King # j in nation #i ruled in the year interval: `[ T[i][j] , T[i][j+1] )` , note that it is an exclusive interval. The battles are all saved in a single list, and each battle is of the format `(n_1,k_1,n_2,k_2)`, where `(n_i,k_i)` represents that we are using king number `k_i` in nation `n_i`.
Define the actual starting year of each nation as `Y_i`. We do not really care about the values of `Y_i`, and in fact, in a consistent setting, there may be many possible starting times. We care more about the difference between the starting years of two nations. Let us call this difference `X_(ij)`.
For two nations `(n_1,n_2)` involved in a battle and their respective kings `(k_1,k_2)`, we assert that there is at least one year in common between the rule intervals of the two kings. Let us name the difference between `Y_(n_2)` and `Y_(n_1)` as `x` (short for `X_{:{:n_1:}{:n_2:}:}`). The real starting time for king 1’s rule, for example, is actually: `Y_(n_1) + T[n_1][k_1]`. This means that there are two intervals:
`[ Y_(n_1) + T[n_1][k_1] , Y_(n_1) + T[n_1][k_1+1] )`
`[ Y_(n_2) + T[n_2][k_2] , Y_(n_2) + T[n_2][k_2+1] )`
These two intervals must intersect - have a year in common. As we mentioned, the difference between the intervals is what matters. So let us say that `x = Y_(n_2) - Y_(n_1)`:
`[ T[n_1][k_1] , T[n_1][k_1+1] )`
`[ x + T[n_2][k_2] , x + T[n_2][k_2+1] )`
The valid values of `x` are consecutive and actually another integer interval. This may need an image:
In the specific case in the image, the values of `x` from 2 to 7 are valid. In general, in order for there to be an intersection between the two intervals, we need x to be between two bounds. From the image, we can see that x is as small as possible when the second king’s interval is as right as possible. This happens when the intersection between the intervals is unique - The left-most integer of the first interval coincides with the right-most integer of the second interval. In other words:
` T[n_1][k_1] = x + T[n_2][K_2+1] - 1 `
` x = T[n_1][k_1] - T[n_2][K_2+1] + 1 `
The maximum possible value of x happens when the right-most integer of the first interval and the left-most integer of the second interval are equal:
` T[n_1][k_1+1] - 1 = x + T[n_2][K_2]`
` x = T[n_1][k_1] - 1 - T[n_2][K_2] `
We will call these values the minimum and maximum x: minx and maxx. According to this battle, the value of x cannot be smaller than minx or larger than maxx.
Battles are symmetrical, so the battle also determines the required constraints for the difference between nation `n_2` and `n_1`. However, consider that there is a relation ship between the minimum difference between `Y_i` and `Y_j` and the maximum difference between `Y_j` and `Y_i`. If we minimize `(Y_j - Y_i)` we are also maximizing `(Y_i - Y_j)` (The sign changes). The maximum value of `X_(ji)` is equal to the minimum value of `X_(ij)` multiplied by -1. In other words, minx is the minimum allowed value for `X[n_1][n_2]` and -maxx is the minimum allowed value for `X[n_2][n_1]`. From these values, we can also find the respective maximums.
With a single battle, we have found constraints for `X_(ij)` and `X_(ji)` for two distinct nations i and j. There may be multiple battles between the two nations. Each battle says that `X_(ij) >= a` for some value `a`, in order to follow all battles at the same time, then `X_(ij) >= max(a_1, a_2, …)`. We need to follow the maximum constraint out of all we find in each battle. We will define this total constraint as `m_(ij)`, the minimum allowed value for `X_(ij)`.
We have processed all the battles and have found constraints `m_(ij)` for each pair of nations `(i,j)` that determine the minimum allowed difference between years `Y_j` and `Y_i`. How do we find if all the values are consistent with each other?
`m_(ij)` is the minimum value for the difference and `-m_(ji)` the maximum. If `-m_(ji) < m_(ij)`, that would mean there are no valid values.
When there are more than 2 nations, then we should also worry about constraints that can be inferred from the initial ones.
There is a relationship between three nations based on the pair-wise differences. For three nations i, j and k: `m_(ik)` is the minimum allowed difference between k and i, `m_(kj)` is the minimum allowed difference between j and k. If j and i were too far apart, then it wouldn’t be possible to fulfill the conditions `m_(ik)` and `m_(kj)`, so we need the distance between j and i to be at most `(m_(ik) + m_(kj))`. This updates the constraint `m_(ij)`:
`m_(ij) = max( m_(ij), m_(ik) + m_(kj) )`
Then we just use Floyd’s algorithm, to update all the constraints until we find better values for each `m_(ij)`.
After updating the values for `m_(ij)`, we can use the pair-wise condition again: If `-m_(ji) < m_(ij)`, then there is a new inconsistency. There is no need to run this inconsistency check before Floyd’s algorithm, it will never remove any inconsistency.
Another method to detect inconsistencies is that `m_(ii)` should be at most 0. It would make no sense for the difference between a nation’s starting year and itself to be positive, so if the constraints tell us that the only way the battles work is if this difference was positive, then we are sure we have an inconsistency.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
import string INF = 10000000; def parseBattle(s): #get nations and kings involvedin a battle. n1 = ord(s[0]) - ord('A') k1 = ord(s[1]) - ord('0') n2 = ord(s[3]) - ord('A') k2 = ord(s[4]) - ord('0') return (n1, k1, n2, k2) def verifyClaim(nationTimes, battles, q): n = len(nationTimes) minDist = [[-INF] * n for i in xrange(0, n)] # For each of the battles(including the query): for b in battles + [q]: (n1, k1, n2, k2) = parseBattle(b) # There must be an overlap between intervals #[nationTimes[n1][k1], nationTimes[n1][k1 + 1]) # and[nationTimes[n2][k2], nationTimes[n2][k2 + 1]) # case 1: # x + nationTimes[n2][k2] = nationTimes[n1][k1 + 1] - 1 maxx = nationTimes[n1][k1 + 1] - 1 - nationTimes[n2][k2] # case 2: # nationTimes[n1][k1] = x + nationTimes[n2][k2 + 1] - 1 minx = nationTimes[n1][k1] - nationTimes[n2][k2 + 1] + 1 # cannot be less than minx minDist[n1][n2] = max(minDist[n1][n2], minx) # cannot be more than - maxx minDist[n2][n1] = max(minDist[n2][n1], -maxx) # Floyd 's algorithm for the transitive closure for k in xrange(0, n): for i in xrange(0, n): for j in xrange(0, n): # Distance between i and j cannot be smaller than... minDist[i][j] = max(minDist[i][j], minDist[i][k] + minDist[k][j]) # We detect inconsistency by using this logic.If a nation must start # after its own time, the whole thing is wrong: for i in xrange(0, n): if minDist[i][i] > 0: return 'N' # Or we could use the following one: for i in xrange(0, n): for j in xrange(0, n): if - minDist[j][i] < minDist[i][j]: # this measn the valid interval for difference between j and i # does not exist return 'N' # only one of the methods is needed return 'Y' class History: def verifyClaims(self, dynasties, battles, queries): # make a complete list of battles in which each index is a single battle: battles = string.join(battles, '') .split(' ') # turn dynasties string array into a 2 D array nationTimes, stores the # integer times for each nation: n = len(dynasties); nationTimes = [[]] * n for i in xrange(0, n): nationTimes[i] = [int(s) for s in dynasties[i].split(' ')] # For each query, verify if it is consistent, if so return 'Y' else 'N': res = [verifyClaim(nationTimes, battles, b) for b in queries] # join the previous results in a single string: return string.join(res, '')